package com.wz.leetcode.array;

public class MedianTwoArrays_4 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 在较小的那部分做二分查找
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0, right = m;
        int median1 = 0, median2 = 0;
        while (left <= right) {
            int i = left + ((right - left) >> 1);
            int j = (m+n+1) / 2 - i;
            int im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i-1]);
            int im0 = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j-1]);
            int jm0 = (j == n ? Integer.MAX_VALUE : nums2[j]);
            if (im1 <= jm0) {
                median1 = Math.max(im1, jm1);
                median2 = Math.min(im0, jm0);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }
        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
        System.out.println(findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
        System.out.println(findMedianSortedArrays(new int[]{1}, new int[]{2, 3}));
    }
}
